#include "main/utils.h"
using namespace std;

class DynamicArray {
  public:
    void insert(int num) {
      int size = smallest_heap.size() + largest_heap.size();
      if (size & 1) {
        if (largest_heap.size() > 0 && largest_heap[0] > num) {
          largest_heap.push_back(num);
          push_heap(largest_heap.begin(), largest_heap.end(), less<int>());
          num = largest_heap[0];
          pop_heap(largest_heap.begin(), largest_heap.end(), less<int>());
          largest_heap.pop_back();
        }

        smallest_heap.push_back(num);
        push_heap(smallest_heap.begin(), smallest_heap.end(), greater<int>());
      } else {
        if (smallest_heap.size() > 0 && smallest_heap[0] < num) {
          smallest_heap.push_back(num);
          push_heap(smallest_heap.begin(), smallest_heap.end(), greater<int>());
          num = smallest_heap[0];
          pop_heap(smallest_heap.begin(), smallest_heap.end(), greater<int>());
          smallest_heap.pop_back();
        }

        largest_heap.push_back(num);
        push_heap(largest_heap.begin(), largest_heap.end(), less<int>());
      }
    }

    int getMedian() {
      int size = smallest_heap.size() + largest_heap.size();
      if (size & 0x01) {
        return largest_heap[0];
      } else {
        return (smallest_heap[0] + largest_heap[0]) / 2;
      }
    }

  private:
    vector<int> smallest_heap;
    vector<int> largest_heap;
};

int main() {
  vector<int> vec = {3, 5, 8, 1, 2, 0, 4, 6, 7};
  DynamicArray help_class;
  for (int i = 0; i < vec.size(); ++i) {
    help_class.insert(vec[i]);
  }
  int ret = help_class.getMedian();
  cout << "Get median number from stream: " << ret << endl;

  return 0;
}
